package com.xj.datastructure.sort;

public class InsertSort
{
    public static void main(String []args){
        int[]arr={1,4,5,6,9,12,14,17};
        int i=binaryFind(arr,13,0,arr.length-1);
		int j=binaryInsert(arr,13);
        System.out.println(i+"  "+j);
    }
    /**
     *循环二分查找
     */
    public static int binaryInsert(int[]arr,int v){
        int i=0;
        int p=0;
        int j=arr.length-1;
        while(i <= j){
            p=(i+j)/2;
            if(v<arr[p]){
                j=p-1;
            }else if(v==arr[p]){
                return p;
            }else{
                i=p+1;
            }
        }
        return p;
    }
    /**
     *递归二分查找
     */
    public static int binaryFind(int[]arr,int v,int i,int j){
        int p=(i+j)/2;
        if(i<=j){
            if(v<arr[p]){
                p=binaryFind(arr,v,i,p-1);
            }else if(v==arr[p]){
				return p;
            }else{
                p=binaryFind(arr,v,p+1,j);
            }
        }
        return p;
    }
}